package com.yequan.leetcode.recursion.generateParenthesis_22;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : Administrator
 * @date : 2020/5/2
 */
public class Recode {

    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        helper(0, 0, n, ans, "");
        return ans;
    }

    private void helper(int left, int right, int max, List<String> ans, String s) {
        if (left == max && right == max) {
            ans.add(s);
            return;
        }
        if (left < max) {
            helper(left + 1, right, max, ans, s + "(");
        }
        if (right < left) {
            helper(left, right + 1, max, ans, s + ")");
        }
    }

}
